package maze

import (
	"container/list"
	"fmt"
)

type (
	MazeCoverage [][]bool

	MazePoint struct {
		X int
		Y int
	}

	MazeRunUnit struct {
		Current MazePoint
		From    MazePoint
	}

	MazeRunMode int
)

const (
	MazeRunTypeNormal  MazeRunMode = iota
	MazeRunTypeBreadth             // 广度优先遍历
)

//Generate 生成迷宫
//width: x
//height: y
func Generate(width, height int) MazeCoverage {
	vec := make(MazeCoverage, 0, height)
	for i := 0; i < height; i++ {
		l := make([]bool, 0, width)
		for j := 0; j < width; j++ {
			n := RandomNumber(0, 100)
			l = append(l, n > 70)
		}
		vec = append(vec, l)
	}
	vec[0][0] = false;
	vec[height-1][width-1] = false;
	return vec
}

func NewEmptyMazeCoverage(width, height int) MazeCoverage {
	vec := make(MazeCoverage, height)
	for i := range vec {
		l := make([]bool, width)
		vec[i] = l
	}
	return vec
}

func (mp *MazePoint) Equals(nmp *MazePoint) bool {
	if nmp == nil {
		return false
	}
	if mp.X == nmp.X && mp.Y == nmp.Y {
		return true
	}
	return false
}

func (mp *MazePoint) String() string {
	return fmt.Sprintf("(%d,%d)", mp.X, mp.Y)
}

func (mc MazeCoverage) Height() int {
	return len(mc)
}

func (mc MazeCoverage) Width() int {
	if mc.Height() == 0 {
		return 0
	}
	return len(mc[0])
}

func (mc MazeCoverage) Contains(point *MazePoint) bool {
	if point == nil {
		return false
	}
	if point.Y >= len(mc) || point.X >= len(mc[point.Y]) {
		return false // 越界
	}
	return mc[point.Y][point.X]
}

func (mc MazeCoverage) Fill(point *MazePoint) bool {
	if point == nil {
		return false
	}
	if point.Y >= len(mc) || point.X >= len(mc[point.Y]) {
		return false // 越界
	}
	res := mc[point.Y][point.X]
	mc[point.Y][point.X] = true
	return res
}

func (mc MazeCoverage) Next(current *MazePoint, alreadyCoverage MazeCoverage) []*MazePoint {
	if current == nil {
		return nil
	}
	if current.Y >= len(mc) || current.X >= len(mc[current.Y]) { // 越界
		return nil
	}
	if mc[current.Y][current.X] { // 墙
		return nil
	}
	mps := make([]*MazePoint, 0, 4)
	alreadyCoverage.Fill(current) // 标记本点
	// 下
	if current.Y+1 < len(mc) && !mc[current.Y+1][current.X] {
		mp := &MazePoint{
			X: current.X,
			Y: current.Y + 1,
		}
		if !alreadyCoverage.Contains(mp) {
			mps = append(mps, mp)
		}
	}
	// 右
	if current.X+1 < len(mc[current.Y]) && !mc[current.Y][current.X+1] {
		mp := &MazePoint{
			X: current.X + 1,
			Y: current.Y,
		}
		if !alreadyCoverage.Contains(mp) {
			mps = append(mps, mp)
		}
	}
	// 上
	if current.Y-1 >= 0 && !mc[current.Y-1][current.X] {
		mp := &MazePoint{
			X: current.X,
			Y: current.Y - 1,
		}
		if !alreadyCoverage.Contains(mp) {
			mps = append(mps, mp)
		}
	}
	// 左
	if current.X-1 >= 0 && !mc[current.Y][current.X-1] {
		mp := &MazePoint{
			X: current.X - 1,
			Y: current.Y,
		}
		if !alreadyCoverage.Contains(mp) {
			mps = append(mps, mp)
		}
	}
	return mps
}

func (mc *MazeCoverage) handleRes(point *MazePoint, fromMap map[*MazePoint]*MazePoint, res *[]*MazePoint) {
	var (
		p  = point
		ok bool
	)
	for {
		*res = append(*res, p)
		p, ok = fromMap[p]
		if !ok {
			break
		}
	}
}

func (mc *MazeCoverage) recurseNormal(point *MazePoint, coverage MazeCoverage, fromMap map[*MazePoint]*MazePoint, res *[]*MazePoint) {
	if point.Y == mc.Height()-1 && point.X == mc.Width()-1 {
		// 已到达
		mc.handleRes(point, fromMap, res)
		return
	}

	ps := mc.Next(point, coverage)
	for _, p := range ps {
		fromMap[p] = point
		mc.recurseNormal(p, coverage, fromMap, res)
	}
}

//recurseBreadth 广度优先
func (mc *MazeCoverage) recurseBreadth(point *MazePoint, coverage MazeCoverage, fromMap map[*MazePoint]*MazePoint, res *[]*MazePoint) {
	l := list.New()
	l.PushBack(point)
	for {
		f := l.Front()
		if f == nil {
			break
		}
		l.Remove(f)

		point := f.Value.(*MazePoint)
		if coverage.Contains(point) {
			// 已经存在, 忽略
			continue
		}
		if point.Y == mc.Height()-1 && point.X == mc.Width()-1 {
			// 已到达
			mc.handleRes(point, fromMap, res)
			return
		}

		ps := mc.Next(point, coverage)
		for _, p := range ps {
			l.PushBack(p)
			fromMap[p] = point
		}
	}
}

func (mc *MazeCoverage) Run(mode MazeRunMode) ( []*MazePoint) {
	var (
		currentPoint = MazePoint{
			X: 0,
			Y: 0,
		}
		coverage = NewEmptyMazeCoverage(mc.Width(), mc.Height())
		fromMap  = map[*MazePoint]*MazePoint{}
		res      = make([]*MazePoint, 0, 2*mc.Height())
	)
	switch mode {
	case MazeRunTypeNormal:
		mc.recurseNormal(&currentPoint, coverage, fromMap, &res)
	case MazeRunTypeBreadth:
		mc.recurseBreadth(&currentPoint, coverage, fromMap, &res)
	}

	return res
}
